Common key block encryption is provided as a technology for concealing communication data and accumulated data. A representative one of the technologies is DES (Data Encryption Standard). DES employs the structure called the Feistel structure. The Feistel structure is characterized in that input data is divided into two and the mixing processing is performed. Various patents for the Feistel-type common-key block encryption processing have been applied, and the recently-applied patents include the encryption processing devices described in Patent Documents 1 and 2.
The structure created by increasing the number of data divisions, which are input into the Feistel structure, to two or more is called the generalized Feistel structure or the modified Feistel structure (hereinafter, the former “generalized Feistel structure” is used throughout this specification).
FIG. 15 is a diagram showing the one-round configuration of the generalized Feistel structure (n-way generalized Feistel structure) for encrypting/decrypting n-divided data. The number of divisions n=2 corresponds to DES described above.
In round processing 9, input data x1 is output directly as output data yn and, at the same time, is mixed with the key data Kr by an F function 90, which is a non-linear processing function, and combined with input data x2 by an exclusive OR 91 to output the result as output data y1. Other input data xi(i>2) is output directly as output data yi-1. In the example shown in FIG. 15, non-linear transformation is performed for one piece of the divided data in one round.
FIG. 16 is a diagram showing an example of another type of the generalized Feistel structure. In the example shown in FIG. 16, non-linear transformation is performed for n/2 pieces of (divided) data in one round.
To distinguish the two generalized Feistel structures given above in the following description, the generalized Feistel structure having the structure shown in FIG. 15 is called Type-I and the generalized Feistel structure having the structure shown in FIG. 16 is called Type-II.
Non-Patent Document 1 is a document proposing an impossible differential characteristic search method for a block encryption having the generalized Feistel structure described above. Non-Patent Document 2 discloses a design method for the linear transformation layer of a round function. Note that the round function disclosed in Non-Patent Document 2 is presupposed to have the SPN structure and so its basic structure is different from the generalized Feistel structure of the present invention.
Patent Document 1
    Japanese Patent Kokai Publication No. JP2007-192893APatent Document 2:    Japanese Patent Kokai Publication No. JP2007-199156ANon-Patent Document 1:    Yukiyasu Tsunoo, Etsuko Tsujihara, Hiroki Nakashima, and Hiroyasu Kubo “Impossible Differentials for Two Types of Extended Feistel Structure”, The 2007 Symposium on Cryptography and Information Security, Jan. 23, 2007Non-Patent Document 2:    Masayuki KANDA, Youichi TAKASHIMA, Tsutomu MATSUMOTO, Kazumaro AOKI, and Kazuo OHTA “A round function structure consisting of few s-boxes (Part III)” Technical Report of The Institute of Electronics, Information and Communication Engineers, ISEC98-3, pp. 21-30